package com.chenken;

/**
 * 	0-1背包问题
 *  
 *	有n件物品和一个最大承重为W的背包，每件物品的重量为Wi,价值是Vi
 *	在保证总重量不超过W的前提下，选择某些物品装入背包，背包的最大总价值是多少?
 *	注意：每个物品只有一件，也就是每个物品只能选择0件或者1件
 *	假设values是价值数组，weights是重量数组
 *	编号为K的物品，价值是values[k],重量是weights[k]	,k范围为[0,n)
 *
 *	假设dp(i,j)是最大承重为j，有前i件物品可选的最大总价值
 *	状态转移方程:
 *  i-1是将要添加的一件物品，第i件物品
 *	如果 j < weight[i-1]     表示该物品不能选 	dp(i,j) = dp(i-1,j)
 *	如果 j >= weight[i-1]   表示该物品可以选		
 *		dp(i,j) = values[i-1] + dp(i-1,j-weights[i-1])
 *	但是有可能不选该物品，而采取之前方案  价值更大(选了要将之前的物品拿出去)
 *	所以  dp(i,j) = max{dp(i-1,j),values[i-1] + dp(i-1,j-weights[i-1])}
 */
public class Knapsack {

	static int maxValue(int[] values,int[] weights,int capacity) {
		if(values == null || weights == null || values.length == 0 || weights.length == 0) {
			return 0;
		}
		if(values.length != weights.length || capacity <= 0) {
			return 0;
		}
		int dp[][] = new int[values.length+1][capacity+1];
		for(int i = 1;i<=values.length;i++) {
			for(int j = 1;j<=capacity;j++) {
				if(j < weights[i-1]) {
					dp[i][j] = dp[i-1][j];
				}else {
					dp[i][j] = values[i-1] + dp[i-1][j-weights[i-1]];
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j]);
				}
			}
		}
		return dp[values.length][capacity];
	}
	
	/**
	 * 	要求装进背包的物品重量恰好等于capacity
	 * @param values
	 * @param weights
	 * @param capacity
	 * @return
	 */
	static int maxValueExactly(int[] values,int[] weights,int capacity) {
		if(values == null || weights == null || values.length == 0 || weights.length == 0) {
			return 0;
		}
		if(values.length != weights.length || capacity <= 0) {
			return 0;
		}
		int dp[][] = new int[values.length+1][capacity+1];
		for(int j = 1;j < dp[0].length;j++) {
			//	第0行的每一列都赋值为负无穷大
			dp[0][j] = Integer.MIN_VALUE;
		}
		for(int i = 1;i<=values.length;i++) {
			for(int j = 1;j<=capacity;j++) {
				if(j < weights[i-1]) {
					dp[i][j] = dp[i-1][j];
				}else {
					dp[i][j] = values[i-1] + dp[i-1][j-weights[i-1]];
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j]);
				}
			}
		}
		return dp[values.length][capacity] < 0 ? -1:dp[values.length][capacity];
	}
	
	public static void main(String[] args) {
		int[] values = {6,3,5,4,6};
		int[] weights = {2,2,6,5,4};
		int capacity = 10;
		int maxValue = maxValue(values, weights, capacity);
		int maxValue2 = maxValueExactly(values, weights, capacity);
		System.out.println(maxValue);
		System.out.println(maxValue2);
	}
	
}
